1076D - Edge Deletion - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
#define pii pair<int, int>
#define pli pair<long long, int>
#define piii pair<int, pair<int, int>>
bool vis[300005];
int n, m, k;
vector<piii> g[300005];
long long dis[300005];
vector<pii> G[300005];
vector<int> ans;
priority_queue<pli, vector<pli>, greater<pli> > q;
void dfs(int x){
	if(ans.size() == k) return ;
	vis[x] = 1;
	for(int i = 0; i < G[x].size(); i++){
		int y = G[x][i].first;
		if(vis[y]) continue;
		if(ans.size() == k) return ;
		ans.push_back(G[x][i].second);
		if(ans.size() == k) return ;
		dfs(y);
	}
}
int main(){
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i <= m; i++){
		int x, y, w;
		scanf("%d%d%d", &x, &y, &w);
		g[x].push_back({y, {w, i}});
		g[y].push_back({x, {w, i}});
	}
	for(int i = 2; i <= n; i++) dis[i] = INF;
	q.push({0, 1});
	while(!q.empty()){
		int u = q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(int i = 0; i < g[u].size(); i++){
			int y = g[u][i].first, w = g[u][i].second.first;
			if(dis[y] > dis[u] + w) {
				dis[y] = dis[u] + w;
				q.push({dis[y], y});
			}
		}
	}
	for(int i = 1; i <= n; i++){
		vis[i] = 0;
		for(int j = 0; j < g[i].size(); j++){
			int y = g[i][j].first, w = g[i][j].second.first;
			int id = g[i][j].second.second;
			if(dis[i] + w == dis[y]){
				G[i].push_back({y, id});
			}
		}
	}
	dfs(1);
	cout << ans.size() << endl;
	for(int i = 0; i < ans.size(); i++) {
		cout << ans[i] << " ";
	}
    return 0;
}